SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Integer programming</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Integer programming</span></span>

</h1>

</header>

<p>An <b>integer programming</b> problem is a <a href="Mathematical_optimization" title="Mathematical optimization">mathematical optimization</a> or <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">feasibility</a> program in which some or all of the variables are restricted to be <a href="Integer" title="Integer">integers</a>. In many settings the term refers to <b>integer <a href="Linear_programming" title="Linear programming">linear programming</a></b> (ILP), in which the <a href="Objective_function" class="mw-redirect" title="Objective function">objective function</a> and the constraints (other than the integer constraints) are <a href="Linear_function_(calculus)" title="Linear function (calculus)">linear</a>.

</p><p>Integer programming is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>. In particular, the special case of 0–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of <a href="Karp's_21_NP-complete_problems" title="Karp's 21 NP-complete problems">Karp's 21 NP-complete problems</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>If some decision variables are not discrete, the problem is known as a <b>mixed-integer programming</b> problem.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Canonical_and_standard_form_for_ILPs">Canonical and standard form for ILPs</h2></div>

<p>In integer linear programming, the <i>canonical form</i> is distinct from the <i>standard form</i>. An integer linear program in canonical form is expressed thus (note that it is the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> vector which is to be decided):<sup id="cite_ref-optBook_3-0" class="reference"><a href="#cite_note-optBook-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<mtr>

<mtd>

<mtext>maximize</mtext>

<mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}</annotation>

</semantics>

</math></span><img src="./4df3e1accc1310a2f9e6feaf632a7694ddea29f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.671ex; width:23.612ex; height:10.509ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}" loading="lazy"></span></dd></dl>

<p>and an ILP in standard form is expressed as

</p>

<mtr>

<mtd>

<mtext>maximize</mtext>

<mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./66a06dd1106b092d99e848df7a99813bcf0d67a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.171ex; width:27.508ex; height:13.509ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./690673949ed47fcbf3482702d9d5a7df505a25b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.638ex; height:2.676ex;" alt="{\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}" loading="lazy"></span> are vectors and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{m\times n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{m\times n}}</annotation>

</semantics>

</math></span><img src="./8025ab71ecd74b01e89f6918676203ad16cdc4a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{m\times n}}" loading="lazy"></span> is a matrix. As with linear programs, ILPs not in standard form can be <a href="Simplex_algorithm#Standard_form" title="Simplex algorithm">converted to standard form</a> by eliminating inequalities, introducing slack variables (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {s} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {s} }</annotation>

</semantics>

</math></span><img src="./644ae690160e658898a141e568a7fb0ee6040004.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.056ex; height:1.676ex;" alt="{\displaystyle \mathbf {s} }" loading="lazy"></span>) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>The plot on the right shows the following problem.

</p>

<mtr>

<mtd>

<mtext>maximize</mtext>

<mrow>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./4127b861edc1e2982b24f6f02b1c114c9f9260cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.671ex; width:25.978ex; height:16.509ex;" alt="{\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>The feasible integer points are shown in red, and the red dashed lines indicate their <a href="Convex_hull" title="Convex hull">convex hull</a>, which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1,2)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1,2)}</annotation>

</semantics>

</math></span><img src="./1d0c72462a85992b95f90cc4a69048c9d83e8cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (1,2)}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2,2)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2,2)}</annotation>

</semantics>

</math></span><img src="./94d0ca163bd6ff9c2757666390d7a4c0ee7273b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (2,2)}" loading="lazy"></span> that both have an objective value of 2. The unique optimum of the relaxation is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1.8,2.8)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1.8,2.8)}</annotation>

</semantics>

</math></span><img src="./c4d71060d43cde110beef368279926816790bd12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.787ex; height:2.843ex;" alt="{\displaystyle (1.8,2.8)}" loading="lazy"></span> with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP. <a href="Simplex#Projection_onto_the_standard_simplex" title="Simplex">See projection into simplex</a>

</p>

<div class="mw-heading mw-heading2"><h2 id="Proof_of_NP-hardness">Proof of NP-hardness</h2></div>

<p>The following is a reduction from minimum <a href="Vertex_cover" title="Vertex cover">vertex cover</a> to integer programming that will serve as the proof of NP-hardness.

</p><p>Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math></span><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"></span> be an undirected graph. Define a linear program as follows:

</p>

<mtr>

<mtd>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall u,v\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./c143210bd0b6574c658d3f404179685d2f9ab7ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.338ex; width:30.872ex; height:11.843ex;" alt="{\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall u,v\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Given that the constraints limit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{v}}</annotation>

</semantics>

</math></span><img src="./fb03554f7c3a0a8341c5795fd7eb0f81461a6f5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.169ex; height:2.009ex;" alt="{\displaystyle y_{v}}" loading="lazy"></span> to either 0 or 1, any feasible solution to the integer program is a subset of vertices. The first constraint implies that at least one end point of every edge is included in this subset. Therefore, the solution describes a vertex cover. Additionally given some vertex cover C, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{v}}</annotation>

</semantics>

</math></span><img src="./fb03554f7c3a0a8341c5795fd7eb0f81461a6f5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.169ex; height:2.009ex;" alt="{\displaystyle y_{v}}" loading="lazy"></span> can be set to 1 for any <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in C}</annotation>

</semantics>

</math></span><img src="./3caca0196e350441aba705c273749dbac2fc27d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.735ex; height:2.176ex;" alt="{\displaystyle v\in C}" loading="lazy"></span> and to 0 for any <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\not \in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\not \in C}</annotation>

</semantics>

</math></span><img src="./1237f3c36e7d17346d83818fd62faab9c756a26d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.735ex; height:2.676ex;" alt="{\displaystyle v\not \in C}" loading="lazy"></span> thus giving us a feasible solution to the integer program. Thus we can conclude that if we minimize the sum of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{v}}</annotation>

</semantics>

</math></span><img src="./fb03554f7c3a0a8341c5795fd7eb0f81461a6f5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.169ex; height:2.009ex;" alt="{\displaystyle y_{v}}" loading="lazy"></span> we have also found the minimum vertex cover.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

<p><b>Mixed-integer linear programming</b> (<b>MILP</b>) involves problems in which only some of the variables, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span>, are constrained to be integers, while other variables are allowed to be non-integers.

</p><p><b>Zero–one linear programming</b> (or <b>binary integer programming</b>) involves problems in which the variables are restricted to be either 0 or 1. Any bounded integer variable can be expressed as a combination of <a href="Binary_data" title="Binary data">binary variables</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> For example, given an integer variable, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq x\leq U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq x\leq U}</annotation>

</semantics>

</math></span><img src="./24c7d1ec90762e44d0909944ecc2a1bbf992148d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.472ex; height:2.343ex;" alt="{\displaystyle 0\leq x\leq U}" loading="lazy"></span>, the variable can be expressed using <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor \log _{2}U\rfloor +1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor \log _{2}U\rfloor +1}</annotation>

</semantics>

</math></span><img src="./6f4b92269bad1208b37d26ea5af1c7f10df33d55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.263ex; height:2.843ex;" alt="{\displaystyle \lfloor \log _{2}U\rfloor +1}" loading="lazy"></span> binary variables:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.}</annotation>

</semantics>

</math></span></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>There are two main reasons for using integer variables when modeling problems as a linear program:

</p>

<ol><li>The integer variables represent quantities that can only be integer. For example, it is not possible to build 3.7 cars.</li>

<li>The integer variables represent decisions (e.g. whether to include an edge in a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a>) and so should only take on the value 0 or 1.</li></ol>

<p>These considerations occur frequently in practice and so integer linear programming can be used in many applications areas, some of which are briefly described below.

</p>

<div class="mw-heading mw-heading3"><h3 id="Production_planning">Production planning</h3></div>

<p>Mixed-integer programming has many applications in industrial productions, including job-shop modelling. One important example happens in agricultural <a href="Production_planning" title="Production planning">production planning</a> and involves determining production yield for several crops that can share resources (e.g. land, labor, capital, seeds, fertilizer, etc.). A possible objective is to maximize the total production, without exceeding the available resources. In some cases, this can be expressed in terms of a linear program, but the variables must be constrained to be integer.

</p>

<div class="mw-heading mw-heading3"><h3 id="Scheduling">Scheduling</h3></div>

<p>These problems involve service and vehicle scheduling in transportation networks. For example, a problem may involve assigning buses or subways to individual routes so that a timetable can be met, and also to equip them with drivers. Here binary decision variables indicate whether a bus or subway is assigned to a route and whether a driver is assigned to a particular train or subway. The zero–one programming technique has been successfully applied to solve a project selection problem in which projects are mutually exclusive and/or technologically interdependent.

</p>

<div class="mw-heading mw-heading3"><h3 id="Territorial_partitioning">Territorial partitioning</h3></div>

<p>Territorial partitioning or districting problems consist of partitioning a geographical region into districts in order to plan some operations while considering different criteria or constraints. Some requirements for this problem are: contiguity, compactness, balance or equity, respect of natural boundaries, and socio-economic homogeneity. Some applications for this type of problem include: political districting, school districting, health services districting and waste management districting.

</p>

<div class="mw-heading mw-heading3"><h3 id="Telecommunications_networks">Telecommunications networks</h3></div>

<p>The goal of these problems is to design a network of lines to install so that a predefined set of communication requirements are met and the total cost of the network is minimal.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> This requires optimizing both the topology of the network along with setting the capacities of the various lines. In many cases, the capacities are constrained to be integer quantities. Usually there are, depending on the technology used, additional restrictions that can be modeled as linear inequalities with integer or binary variables.

</p>

<div class="mw-heading mw-heading3"><h3 id="Cellular_networks">Cellular networks</h3></div>

<p>The task of frequency planning in <a href="GSM" title="GSM">GSM</a> mobile networks involves distributing available frequencies across the antennas so that users can be served and interference is minimized between the antennas.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> This problem can be formulated as an integer linear program in which binary variables indicate whether a frequency is assigned to an antenna.

</p>

<div class="mw-heading mw-heading3"><h3 id="Other_applications">Other applications</h3></div>

<ul><li><a href="Cashflow_matching" title="Cashflow matching">Cash flow matching</a></li>

<li><a href="Energy_system" title="Energy system">Energy system</a> optimization<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Unmanned_aerial_vehicle" title="Unmanned aerial vehicle">UAV</a> <a href="Guidance_system" title="Guidance system">guidance</a><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Transit_map" title="Transit map">Transit map</a> <a href="Graph_drawing" title="Graph drawing">layouting</a><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<p>The naive way to solve an ILP is to simply remove the constraint that <b>x</b> is integer, solve the corresponding LP (called the <a href="Linear_programming_relaxation" title="Linear programming relaxation">LP relaxation</a> of the ILP), and then round the entries of the solution to the LP relaxation. But, not only may this solution not be optimal, it may not even be feasible; that is, it may violate some constraint.

</p>

<div class="mw-heading mw-heading3"><h3 id="Using_total_unimodularity">Using total unimodularity</h3></div>

<p>While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }</annotation>

</semantics>

</math></span><img src="./c442e2be068004cad2967b721ed7e96439fd1da1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.731ex; height:2.676ex;" alt="{\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\mathbf {x} =\mathbf {b} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\mathbf {x} =\mathbf {b} }</annotation>

</semantics>

</math></span><img src="./45d894430af69e29d6dda5aacbf4bb19336226a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.738ex; height:2.176ex;" alt="{\displaystyle A\mathbf {x} =\mathbf {b} }" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {b} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {b} }</annotation>

</semantics>

</math></span><img src="./13ebf4628a1adf07133a6009e4a78bdd990c6eb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.485ex; height:2.176ex;" alt="{\displaystyle \mathbf {b} }" loading="lazy"></span> have all integer entries and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is <a href="Unimodular_matrix#Total_unimodularity" title="Unimodular matrix">totally unimodular</a>, then every <a href="Basic_feasible_solution" title="Basic feasible solution">basic feasible solution</a> is integral. Consequently, the solution returned by the <a href="Simplex_algorithm" title="Simplex algorithm">simplex algorithm</a> is guaranteed to be integral. To show that every basic feasible solution is integral, let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> be an arbitrary basic feasible solution . Since <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> is feasible,

we know that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\mathbf {x} =\mathbf {b} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\mathbf {x} =\mathbf {b} }</annotation>

</semantics>

</math></span><img src="./45d894430af69e29d6dda5aacbf4bb19336226a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.738ex; height:2.176ex;" alt="{\displaystyle A\mathbf {x} =\mathbf {b} }" loading="lazy"></span>. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}</annotation>

</semantics>

</math></span><img src="./dfa84a77e8f9f05bb2dcbda53c5b400f8e899adf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:23.091ex; height:3.176ex;" alt="{\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}" loading="lazy"></span> be the elements corresponding to the basis columns for the basic solution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span>. By definition of a basis, there is some square submatrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> of

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> with linearly independent columns such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\mathbf {x} _{0}=\mathbf {b} }">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B\mathbf {x} _{0}=\mathbf {b} }</annotation>

</semantics>

</math></span><img src="./8af5d22babd55bf3b5053b5ca704ecaf84625930.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.813ex; height:2.509ex;" alt="{\displaystyle B\mathbf {x} _{0}=\mathbf {b} }" loading="lazy"></span>.

</p><p>Since the columns of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> are linearly independent and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is square, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is nonsingular,

and therefore by assumption, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is <a href="Unimodular_matrix" title="Unimodular matrix">unimodular</a> and so <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \det(B)=\pm 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \det(B)=\pm 1}</annotation>

</semantics>

</math></span><img src="./e927687d90f621f4f0e805fd5797da6439044fb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.872ex; height:2.843ex;" alt="{\displaystyle \det(B)=\pm 1}" loading="lazy"></span>. Also, since <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is nonsingular, it is invertible and therefore <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }">

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }</annotation>

</semantics>

</math></span><img src="./99b9f42a7dc5bab9269d33420e770eb2e86f6c50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.146ex; height:3.009ex;" alt="{\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }" loading="lazy"></span>. By definition, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}">

<msup>

</mrow>

</msup>

<mfrac>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}</annotation>

</semantics>

</math></span><img src="./80021829acbf0fc61c8175b355a1cb3cfbedb18f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:23.976ex; height:6.509ex;" alt="{\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}" loading="lazy"></span>. Here <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B^{\mathrm {adj} }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B^{\mathrm {adj} }}</annotation>

</semantics>

</math></span><img src="./aa97a2c045f5a418c074de23a523eec81dc2a370.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.236ex; height:2.676ex;" alt="{\displaystyle B^{\mathrm {adj} }}" loading="lazy"></span> denotes the <a href="Adjugate_matrix" title="Adjugate matrix">adjugate</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> and is integral because <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is integral. Therefore,

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mtext> is integral.</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mtext> is integral.</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>Every basic feasible solution is integral.</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}}</annotation>

</semantics>

</math></span></span>

Thus, if the matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> of an ILP is totally unimodular, rather than use an ILP algorithm, the simplex method can be used to solve the LP relaxation and the solution will be integer.

</p>

<div class="mw-heading mw-heading3"><h3 id="Exact_algorithms">Exact algorithms</h3></div>

<p>When the matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is not totally unimodular, there are a variety of algorithms that can be used to solve integer linear programs exactly. One class of algorithms are <a href="Cutting-plane_method" title="Cutting-plane method">cutting plane methods</a>, which work by solving the LP relaxation and then adding linear constraints that drive the solution towards being integer without excluding any integer feasible points.

</p><p>Another class of algorithms are variants of the <a href="Branch_and_bound" title="Branch and bound">branch and bound</a> method. For example, the <a href="Branch_and_cut" title="Branch and cut">branch and cut</a> method that combines both branch and bound and cutting plane methods. Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes. One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a feasible, although not necessarily optimal, solution can be returned. Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is. Finally, branch and bound methods can be used to return multiple optimal solutions.

</p>

<div class="mw-heading mw-heading3"><h3 id="Exact_algorithms_for_a_small_number_of_variables">Exact algorithms for a small number of variables</h3></div>

<p>Suppose <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is an <i>m</i>-by-<i>n</i> integer matrix and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {b} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {b} }</annotation>

</semantics>

</math></span><img src="./13ebf4628a1adf07133a6009e4a78bdd990c6eb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.485ex; height:2.176ex;" alt="{\displaystyle \mathbf {b} }" loading="lazy"></span> is an <i>m</i>-by-1 integer vector. We focus on the feasibility problem, which is to decide whether there exists an <i>n</i>-by-1 vector <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> satisfying <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\mathbf {x} \leq \mathbf {b} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\mathbf {x} \leq \mathbf {b} }</annotation>

</semantics>

</math></span><img src="./f8eb555d2593e4022e59e054e47c0068ba054ad9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.738ex; height:2.343ex;" alt="{\displaystyle A\mathbf {x} \leq \mathbf {b} }" loading="lazy"></span>.

</p><p>Let <i>V</i> be the maximum absolute value of the coefficients in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {b} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {b} }</annotation>

</semantics>

</math></span><img src="./13ebf4628a1adf07133a6009e4a78bdd990c6eb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.485ex; height:2.176ex;" alt="{\displaystyle \mathbf {b} }" loading="lazy"></span>. If <i>n</i> (the number of variables) is a fixed constant, then the feasibility problem can be solved in time polynomial in <i>m</i> and log <i>V</i>. This is trivial for the case <i>n</i>=1. The case <i>n</i>=2 was solved in 1981 by <a href="Herbert_Scarf" title="Herbert Scarf">Herbert Scarf</a>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> The general case was solved in 1983 by <a href="Hendrik_Lenstra" title="Hendrik Lenstra">Hendrik Lenstra</a>, combining ideas by <a href="L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">László Lovász</a> and <a href="Peter_van_Emde_Boas" title="Peter van Emde Boas">Peter van Emde Boas</a>.<sup id="cite_ref-:0_14-0" class="reference"><a href="#cite_note-:0-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> <a href="Doignon's_theorem" title="Doignon's theorem">Doignon's theorem</a> asserts that an integer program is feasible whenever every subset of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span> constraints is feasible; a method combining this result with algorithms for <a href="LP-type_problem" title="LP-type problem">LP-type problems</a> can be used to solve integer programs in time that is linear in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span> and <a href="Fixed-parameter_tractable" class="mw-redirect" title="Fixed-parameter tractable">fixed-parameter tractable</a> (FPT) in <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span></i>, but possibly <a href="Double_exponential_function" title="Double exponential function">doubly exponential</a> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>, with no dependence on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math></span><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span>.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup>

</p><p>In the special case of 0-1 ILP, Lenstra's algorithm is equivalent to complete enumeration: the number of all possible solutions is fixed (2<i><sup>n</sup></i>), and checking the feasibility of each solution can be done in time poly(<i>m</i>, log <i>V</i>). In the general case, where each variable can be an arbitrary integer, complete enumeration is impossible. Here, Lenstra's algorithm uses ideas from <a href="Geometry_of_numbers" title="Geometry of numbers">Geometry of numbers</a>. It transforms the original problem into an equivalent one with the following property: either the existence of a solution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> is obvious, or the value of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n}}</annotation>

</semantics>

</math></span><img src="./7c5ea190699149306d242b70439e663559e3ffbe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.548ex; height:2.009ex;" alt="{\displaystyle x_{n}}" loading="lazy"></span> (the <i>n</i>-th variable) belongs to an interval whose length is bounded by a function of <i>n</i>. In the latter case, the problem is reduced to a bounded number of lower-dimensional problems. The run-time complexity of the algorithm has been improved in several steps:

</p>

<ul><li>The original algorithm of Lenstra<sup id="cite_ref-:0_14-1" class="reference"><a href="#cite_note-:0-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> had run-time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}</annotation>

</semantics>

</math></span><img src="./1eb1d8d45f8af3fdfc526481bacf29530fb5a640.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.687ex; height:3.509ex;" alt="{\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}" loading="lazy"></span>.</li>

<li>Kannan<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> presented an improved algorithm with run-time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}</annotation>

</semantics>

</math></span><img src="./e3217b5655b1ffea22aca8b666e61bdbe89bfc18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.088ex; height:3.343ex;" alt="{\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}" loading="lazy"></span>.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup></li>

<li>Frank and Tardos<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> presented an improved algorithm with run-time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}</annotation>

</semantics>

</math></span><img src="./dd42486322fac7336150282800396e65c0b86947.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.249ex; height:3.343ex;" alt="{\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}" loading="lazy"></span>.<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: Prop.8">: Prop.8 </span></sup></li>

<li>Dadush<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> presented an improved algorithm with run-time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}</annotation>

</semantics>

</math></span><img src="./ef6f590594b1992cce0ea36d79e22303a36d80f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.148ex; height:3.343ex;" alt="{\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}" loading="lazy"></span>.</li>

<li>Reis and Rothvoss<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> presented an improved algorithm with run-time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}</annotation>

</semantics>

</math></span><img src="./13513aaf8b400088e45823f4c0e0ce6b42892cba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.256ex; height:3.343ex;" alt="{\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}" loading="lazy"></span>.</li></ul>

<p>These algorithms can also be used for <b>mixed integer linear programs</b> (MILP) - programs in which some variables are integer and some variables are real.<sup id="cite_ref-:1_23-0" class="reference"><a href="#cite_note-:1-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> The original algorithm of Lenstra<sup id="cite_ref-:0_14-2" class="reference"><a href="#cite_note-:0-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: Sec.5">: Sec.5 </span></sup> has run-time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}</annotation>

</semantics>

</math></span><img src="./e67988c47852757504ea93cfb5220573ea9eb5e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.213ex; height:3.509ex;" alt="{\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}" loading="lazy"></span>, where n is the number of integer variables, d is the number of continuous variables, and <i>L</i> is the binary encoding size of the problem. Using techniques from later algorithms, the factor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(n^{3})}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(n^{3})}}</annotation>

</semantics>

</math></span><img src="./6fac67875087ae24d0391d4431524b65d6ab02e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.746ex; height:3.009ex;" alt="{\displaystyle 2^{O(n^{3})}}" loading="lazy"></span> can be improved to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(n\log n)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(n\log n)}}</annotation>

</semantics>

</math></span><img src="./71b8cb5d13fc14b9ef1f4ba49bc408350674709b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.776ex; height:2.843ex;" alt="{\displaystyle 2^{O(n\log n)}}" loading="lazy"></span> or to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{n}}</annotation>

</semantics>

</math></span><img src="./88ce30228c74c7fb8b0d262d7d9363f87d30d42f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.613ex; height:2.343ex;" alt="{\displaystyle n^{n}}" loading="lazy"></span>.<sup id="cite_ref-:1_23-1" class="reference"><a href="#cite_note-:1-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Heuristic_methods">Heuristic methods</h3></div>

<p>Since integer linear programming is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, many problem instances are intractable and so heuristic methods must be used instead. For example, <a href="Tabu_search" title="Tabu search">tabu search</a> can be used to search for solutions to ILPs.<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> To use tabu search to solve ILPs, moves can be defined as incrementing or decrementing an integer constrained variable of a feasible solution while keeping all other integer-constrained variables constant. The unrestricted variables are then solved for. Short-term memory can consist of previously tried solutions while medium-term memory can consist of values for the integer constrained variables that have resulted in high objective values (assuming the ILP is a maximization problem). Finally, long-term memory can guide the search towards integer values that have not previously been tried.

</p><p>Other heuristic methods that can be applied to ILPs include

</p>

<ul><li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li>Reactive search optimization</li>

<li><a href="Ant_colony_optimization_algorithms" title="Ant colony optimization algorithms">Ant colony optimization</a></li>

<li><a href="Hopfield_network" title="Hopfield network">Hopfield neural networks</a></li></ul>

<p>There are also a variety of other problem-specific heuristics, such as the <a href="Travelling_salesman_problem#Iterative_improvement" title="Travelling salesman problem">k-opt heuristic</a> for the traveling salesman problem. A disadvantage of heuristic methods is that if they fail to find a solution, it cannot be determined whether it is because there is no feasible solution or whether the algorithm simply was unable to find one. Further, it is usually impossible to quantify how close to optimal a solution returned by these methods are.

</p>

<div class="mw-heading mw-heading2"><h2 id="Sparse_integer_programming">Sparse integer programming</h2></div>

<p>It is often the case that the matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> that defines the integer program is <i><a href="Sparse_matrix" title="Sparse matrix">sparse</a></i>. In particular, this occurs when the matrix has a <a href="Block_matrix" title="Block matrix">block structure</a>, which is the case in many applications. The sparsity of the matrix can be measured as follows. The <i>graph</i> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> has vertices corresponding to columns of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>, and two columns form an edge if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The <i>sparsity measure</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math></span><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"></span> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is the minimum of the <a href="Tree-depth" title="Tree-depth">tree-depth</a> of the graph of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> and the <a href="Tree-depth" title="Tree-depth">tree-depth</a> of the graph of the transpose of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> be the <i>numeric measure</i> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> defined as the maximum absolute value of any entry of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> be the number of variables of the integer program. Then it was shown in 2018<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> that integer programming can be solved in <a href="Strongly_polynomial" class="mw-redirect" title="Strongly polynomial">strongly polynomial</a> and <a href="Fixed-parameter_tractable" class="mw-redirect" title="Fixed-parameter tractable">fixed-parameter tractable</a> time parameterized by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math></span><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"></span>. That is, for some computable function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> and some constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>, integer programming can be solved in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(a,d)n^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a,d)n^{k}}</annotation>

</semantics>

</math></span><img src="./059f35e1459ccafca42f4563cae734f5a143c570.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.051ex; height:3.176ex;" alt="{\displaystyle f(a,d)n^{k}}" loading="lazy"></span>. In particular, the time is independent of the right-hand side <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> and objective function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>. Moreover, in contrast to the classical result of Lenstra, where the number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> of variables is a parameter, here the number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> of variables is a variable part of the input.

</p>

<ul><li><a href="Constrained_least_squares" title="Constrained least squares">Constrained least squares</a></li>

<li><a href="Diophantine_equation" title="Diophantine equation">Diophantine equation</a> – Polynomial equation whose integer solutions are sought</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKarp1972" class="citation book cs1"><a href="Richard_M._Karp" title="Richard M. Karp">Karp, Richard M.</a> (1972). <a rel="nofollow" class="external text" href="http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf">"Reducibility among Combinatorial Problems"</a> <span class="cs1-format">(PDF)</span>. In R. E. Miller; J. W. Thatcher; J.D. Bohlinger (eds.). <i>Complexity of Computer Computations</i>. New York: Plenum. pp. <span class="nowrap">85–</span>103. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4684-2001-2_9">10.1007/978-1-4684-2001-2_9</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4684-2003-6</bdi>.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite book}}</code>: CS1 maint: publisher location (link)</span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://macc.mcmaster.ca/maccfiles/chachuatnotes/07-MILP-I_handout.pdf">"Mixed-Integer Linear Programming (MILP): Model Formulation"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">16 April</span> 2018</span>.</cite></span>

</li>

<li id="cite_note-optBook-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-optBook_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFPapadimitriouSteiglitz1998" class="citation book cs1"><a href="Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, C. H.</a>; <a href="Kenneth_Steiglitz" title="Kenneth Steiglitz">Steiglitz, K.</a> (1998). <i>Combinatorial optimization: algorithms and complexity</i>. Mineola, NY: Dover. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0486402584</bdi>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFErickson2015" class="citation web cs1">Erickson, J. (2015). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150518072946/https://courses.engr.illinois.edu/cs498dl1/sp2015/solutions/hw10sol.pdf">"Integer Programming Reduction"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="https://courses.engr.illinois.edu/cs498dl1/sp2015/solutions/hw10sol.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 18 May 2015.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFWilliams2009" class="citation book cs1">Williams, H.P. (2009). <i>Logic and integer programming</i>. International Series in Operations Research & Management Science. Vol. 130. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-92280-5</bdi>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBorndörferGrötschel2012" class="citation web cs1">Borndörfer, R.; <a href="Martin_Gr%C3%B6tschel" title="Martin Grötschel">Grötschel, M.</a> (2012). <a rel="nofollow" class="external text" href="http://www.zib.de/groetschel/teaching/SS2012/120503Vorlesung-DesigningTelcomNetworks-reduced.pdf">"Designing telecommunication networks by integer programming"</a> <span class="cs1-format">(PDF)</span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFSharma2010" class="citation web cs1">Sharma, Deepak (2010). <a rel="nofollow" class="external text" href="https://www.slideshare.net/deepakecrbs/gsm-frequency-planning">"Frequency Planning"</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFMoraisKádárFariaVale2010" class="citation journal cs1">Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, H. M. (2010-01-01). <a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0960148109001001">"Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming"</a>. <i>Renewable Energy</i>. <b>35</b> (1): <span class="nowrap">151–</span>156. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010REne...35..151M">2010REne...35..151M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.renene.2009.02.031">10.1016/j.renene.2009.02.031</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/10400.22%2F1585">10400.22/1585</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0960-1481">0960-1481</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFOmuChoudharyBoies2013" class="citation journal cs1">Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0301421513003418">"Distributed energy resource system optimisation using mixed integer linear programming"</a></span>. <i>Energy Policy</i>. <b>61</b>: <span class="nowrap">249–</span>266. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013EnPol..61..249O">2013EnPol..61..249O</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.enpol.2013.05.009">10.1016/j.enpol.2013.05.009</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0301-4215">0301-4215</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29369795">29369795</a>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchouwenaarsValentiFeronHow2005" class="citation book cs1">Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). "Implementation and Flight Test Results of MILP-based UAV Guidance". <i>2005 IEEE Aerospace Conference</i>. pp. <span class="nowrap">1–</span>13. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FAERO.2005.1559600">10.1109/AERO.2005.1559600</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7803-8870-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13447718">13447718</a>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFRadmaneshKumar2016" class="citation journal cs1">Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ast.2015.12.021">"Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming"</a>. <i>Aerospace Science and Technology</i>. <b>50</b>: <span class="nowrap">149–</span>160. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016AeST...50..149R">2016AeST...50..149R</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ast.2015.12.021">10.1016/j.ast.2015.12.021</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1270-9638">1270-9638</a>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFBastBrosiStorandt2017" class="citation arxiv cs1">Bast, Hannah; Brosi, Patrick; Storandt, Sabine (2017-10-05). "Efficient Generation of Geographically Accurate Transit Maps". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1710.02226">1710.02226</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CG">cs.CG</a>].</cite></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite id="CITEREFScarf1981" class="citation journal cs1">Scarf, Herbert E. (1981). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1911124">"Production Sets with Indivisibilities, Part I: Generalities"</a></span>. <i>Econometrica</i>. <b>49</b> (1): <span class="nowrap">1–</span>32. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1911124">10.2307/1911124</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0012-9682">0012-9682</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1911124">1911124</a>.</cite></span>

</li>

<li id="cite_note-:0-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_14-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_14-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFLenstra1983" class="citation journal cs1">Lenstra, H. W. (1983-11-01). <a rel="nofollow" class="external text" href="https://pubsonline.informs.org/doi/abs/10.1287/moor.8.4.538">"Integer Programming with a Fixed Number of Variables"</a>. <i>Mathematics of Operations Research</i>. <b>8</b> (4): <span class="nowrap">538–</span>548. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.431.5444">10.1.1.431.5444</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.8.4.538">10.1287/moor.8.4.538</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0364-765X">0364-765X</a>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite id="CITEREFAmentaDe_LoeraSoberón2017" class="citation conference cs1"><a href="Nina_Amenta" title="Nina Amenta">Amenta, Nina</a>; <a href="Jes%C3%BAs_A._De_Loera" title="Jesús A. De Loera">De Loera, Jesús A.</a>; Soberón, Pablo (2017). "Helly's theorem: new variations and applications". In <a href="Heather_Harrington" title="Heather Harrington">Harrington, Heather A.</a>; Omar, Mohamed; Wright, Matthew (eds.). <i>Proceedings of the AMS Special Session on Algebraic and Geometric Methods in Applied Discrete Mathematics held in San Antonio, TX, January 11, 2015</i>. Contemporary Mathematics. Vol. 685. Providence, Rhode Island: American Mathematical Society. pp. <span class="nowrap">55–</span>95. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1508.07606">1508.07606</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fconm%2F685">10.1090/conm/685</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781470423216</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3625571">3625571</a>.</cite></span>

</li>

<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><cite id="CITEREFKannan1987" class="citation journal cs1">Kannan, Ravi (1987-08-01). <a rel="nofollow" class="external text" href="https://pubsonline.informs.org/doi/abs/10.1287/moor.12.3.415">"Minkowski's Convex Body Theorem and Integer Programming"</a>. <i>Mathematics of Operations Research</i>. <b>12</b> (3): <span class="nowrap">415–</span>440. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.12.3.415">10.1287/moor.12.3.415</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0364-765X">0364-765X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:495512">495512</a>.</cite></span>

</li>

<li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><cite id="CITEREFGoemansRothvoss2020" class="citation journal cs1"><a href="Michel_Goemans" title="Michel Goemans">Goemans, Michel X.</a>; Rothvoss, Thomas (2020-11-07). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3421750">"Polynomiality for Bin Packing with a Constant Number of Item Types"</a>. <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>. <b>67</b> (6): 38:1–38:21. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3421750">10.1145/3421750</a></span>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F92865">1721.1/92865</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:227154747">227154747</a>.</cite></span>

</li>

<li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><cite id="CITEREFFrankTardos1987" class="citation journal cs1">Frank, András; Tardos, Éva (1987-03-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF02579200">"An application of simultaneous diophantine approximation in combinatorial optimization"</a></span>. <i>Combinatorica</i>. <b>7</b> (1): <span class="nowrap">49–</span>65. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02579200">10.1007/BF02579200</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1439-6912">1439-6912</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:45585308">45585308</a>.</cite></span>

</li>

<li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><cite id="CITEREFBliemBredereckNiedermeier2016" class="citation journal cs1">Bliem, Bernhard; Bredereck, Robert; <a href="Rolf_Niedermeier" title="Rolf Niedermeier">Niedermeier, Rolf</a> (2016-07-09). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/3060621.3060636">"Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels"</a>. <i>Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence</i>. IJCAI'16. New York, New York, USA: AAAI Press: <span class="nowrap">102–</span>108. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-57735-770-4</bdi>.</cite></span>

</li>

<li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><cite id="CITEREFBredereckKaczmarczykKnopNiedermeier2019" class="citation book cs1">Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3328526.3329649">"High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming"</a>. <i>Proceedings of the 2019 ACM Conference on Economics and Computation</i>. EC '19. Phoenix, AZ, USA: Association for Computing Machinery. pp. <span class="nowrap">505–</span>523. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3328526.3329649">10.1145/3328526.3329649</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-6792-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:195298520">195298520</a>.</cite></span>

</li>

<li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text">Dadush, Daniel (2012-06-14). <a rel="nofollow" class="external text" href="https://homepages.cwi.nl/~dadush/papers/dadush-thesis.pdf">"Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation</a>.</span>

</li>

<li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text">Reis, Victor; Rothvoss, Thomas (2023-03-26). <a rel="nofollow" class="external text" href="https://arxiv.org/abs/2303.14605">"The Subspace Flatness Conjecture and Faster Integer Programming"</a>.</span>

</li>

<li id="cite_note-:1-23"><span class="mw-cite-backlink">^ <a href="#cite_ref-:1_23-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:1_23-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHildebrand2016" class="citation web cs1">Hildebrand, Robert (2016-10-07). <a rel="nofollow" class="external text" href="https://cstheory.stackexchange.com/a/36738/9453">"FPT algorithm for mixed integer program"</a>. <i>Theoretical Computer Science Stack Exchange</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-05-21</span></span>.</cite></span>

</li>

<li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><cite id="CITEREFGlover1989" class="citation journal cs1"><a href="Fred_W._Glover" title="Fred W. Glover">Glover, F.</a> (1989). "Tabu search-Part II". <i>ORSA Journal on Computing</i>. <b>1</b> (3): <span class="nowrap">4–</span>32. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fijoc.2.1.4">10.1287/ijoc.2.1.4</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207225435">207225435</a>.</cite></span>

</li>

<li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><cite id="CITEREFKouteckýLevinOnn2018" class="citation conference cs1">Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "A parameterized strongly polynomial algorithm for block structured integer programs". In Chatzigiannakis, Ioannis; Kaklamanis, Christos; Marx, Dániel; Sannella, Donald (eds.). <i>45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic</i>. LIPIcs. Vol. 107. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 85:1–85:14. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1802.05859">1802.05859</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPICS.ICALP.2018.85">10.4230/LIPICS.ICALP.2018.85</a></span>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFGeorge_L._NemhauserLaurence_A._Wolsey1988" class="citation book cs1"><a href="George_Nemhauser" title="George Nemhauser">George L. Nemhauser</a>; Laurence A. Wolsey (1988). <i>Integer and combinatorial optimization</i>. Wiley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-82819-8</bdi>.</cite></li>

<li><cite id="CITEREFAlexander_Schrijver1998" class="citation book cs1"><a href="Alexander_Schrijver" title="Alexander Schrijver">Alexander Schrijver</a> (1998). <i>Theory of linear and integer programming</i>. John Wiley and Sons. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-98232-6</bdi>.</cite></li>

<li><cite id="CITEREFLaurence_A._Wolsey1998" class="citation book cs1">Laurence A. Wolsey (1998). <i>Integer programming</i>. Wiley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-28366-9</bdi>.</cite></li>

<li><cite id="CITEREFDimitris_BertsimasRobert_Weismantel2005" class="citation book cs1">Dimitris Bertsimas; Robert Weismantel (2005). <i>Optimization over integers</i>. Dynamic Ideas. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-9759146-2-5</bdi>.</cite></li>

<li><cite id="CITEREFJohn_K._Karlof2006" class="citation book cs1">John K. Karlof (2006). <i>Integer programming: theory and practice</i>. CRC Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8493-1914-3</bdi>.</cite></li>

<li><cite id="CITEREFH._Paul_Williams2009" class="citation book cs1">H. Paul Williams (2009). <i>Logic and Integer Programming</i>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-92279-9</bdi>.</cite></li>

<li><cite id="CITEREFMichael_JüngerThomas_M._LieblingDenis_NaddefGeorge_Nemhauser2009" class="citation book cs1">Michael Jünger; Thomas M. Liebling; Denis Naddef; <a href="George_Nemhauser" title="George Nemhauser">George Nemhauser</a>; <a href="William_R._Pulleyblank" title="William R. Pulleyblank">William R. Pulleyblank</a>; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). <i>50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art</i>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-68274-5</bdi>.</cite></li>

<li><cite id="CITEREFDer-San_ChenRobert_G._BatsonYu_Dang2010" class="citation book cs1">Der-San Chen; Robert G. Batson; Yu Dang (2010). <i>Applied Integer Programming: Modeling and Solution</i>. John Wiley and Sons. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-37306-4</bdi>.</cite></li>

<li><cite id="CITEREFGerard_SierksmaYori_Zwols2015" class="citation book cs1">Gerard Sierksma; Yori Zwols (2015). <i>Linear and Integer Optimization: Theory and Practice</i>. CRC Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-498-71016-9</bdi>.</cite></li>

<li><cite id="CITEREFFrançois_ClautiauxIvana_Ljubić2024" class="citation journal cs1">François Clautiaux; Ivana Ljubić (2024). <a rel="nofollow" class="external text" href="https://inria.hal.science/hal-04776866">"Last fifty years of integer linear programming: a focus on recent practical advances"</a>. <i><a href="European_Journal_of_Operational_Research" title="European Journal of Operational Research">European Journal of Operational Research</a></i>. <a href="INRIA" class="mw-redirect" title="INRIA">INRIA</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ejor.2024.11.018">10.1016/j.ejor.2024.11.018</a>.</cite> Overview article.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://mat.tepper.cmu.edu/orclass/integer/integer.html">A Tutorial on Integer Programming</a></li>

<li>Conference <a rel="nofollow" class="external text" href="http://www.mathopt.org/?nav=ipco">Integer Programming and Combinatorial Optimization, IPCO</a></li>

<li><a rel="nofollow" class="external text" href="http://www.iasi.cnr.it/aussois">The Aussois Combinatorial Optimization Workshop</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible expanded navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex<br> minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and<br><a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Revised_simplex_method" title="Revised simplex method">Revised simplex algorithm</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible uncollapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximation_algorithm" title="Approximation algorithm">Approximation algorithm</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph<br> algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum<br> spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-24" href="https://en.wikipedia.org/wiki/?title=Integer_programming&oldid=1297080610">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>